
<!DOCTYPE html>
<html lang="zh-CN" class="loading">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <meta name="viewport" content="width=device-width, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no">
    <title>动态规划背包问题最终话-求方案数和具体的方案 - peony&#39;s blogs</title>
    <meta name="apple-mobile-web-app-capable" content="yes" />
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="google" content="notranslate" />
    <meta name="keywords" content="peony,"> 
    <meta name="description" content="1.求背包问题的方案数有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价,"> 
    <meta name="author" content="peony"> 
    <link rel="alternative" href="atom.xml" title="peony&#39;s blogs" type="application/atom+xml"> 
    <link rel="icon" href="/img/favicon63.png"> 
    
<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.css">

    
<link rel="stylesheet" href="/css/diaspora.css">

    <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
    <script>
         (adsbygoogle = window.adsbygoogle || []).push({
              google_ad_client: "ca-pub-8691406134231910",
              enable_page_level_ads: true
         });
    </script>
    <script async custom-element="amp-auto-ads"
        src="https://cdn.ampproject.org/v0/amp-auto-ads-0.1.js">
    </script>
<meta name="generator" content="Hexo 4.2.0"></head>

<body class="loading">
    <span id="config-title" style="display:none">peony&#39;s blogs</span>
    <div id="loader"></div>
    <div id="single">
    <div id="top" style="display: block;">
    <div class="bar" style="width: 0;"></div>
    <a class="icon-home image-icon" href="javascript:;" data-url="http://yoursite.com"></a>
    <div title="播放/暂停" class="icon-play"></div>
    <h3 class="subtitle">动态规划背包问题最终话-求方案数和具体的方案</h3>
    <div class="social">
        <!--<div class="like-icon">-->
            <!--<a href="javascript:;" class="likeThis active"><span class="icon-like"></span><span class="count">76</span></a>-->
        <!--</div>-->
        <div>
            <div class="share">
                <!--<a title="获取二维码" class="icon-scan" href="javascript:;" ></a>-->
            </div>
            <div id="qr"></div>
        </div>
    </div>
    <div class="scrollbar"></div>
</div>

    <div class="section">
        <div class="article">
    <div class='main'>
        <h1 class="title">动态规划背包问题最终话-求方案数和具体的方案</h1>
        <div class="stuff">
            <span>四月 11, 2020</span>
            

        </div>
        <div class="content markdown">
            <h1 id="1-求背包问题的方案数"><a href="#1-求背包问题的方案数" class="headerlink" title="1.求背包问题的方案数"></a>1.求背包问题的方案数</h1><p>有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。</p>
<p>第 i 件物品的体积是 vi，价值是 wi。</p>
<p>求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。</p>
<p>输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。</p>
<p>输入格式<br>第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。</p>
<p>接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。</p>
<p>输出格式<br>输出一个整数，表示 方案数 模 109+7 的结果。</p>
<p>数据范围<br>0&lt;N,V≤1000<br>0&lt;vi,wi≤1000</p>
<hr>
<p><a href="https://www.acwing.com/problem/content/11/" target="_blank" rel="noopener">来源acwing</a><br>在01背包的基础上新增加一个数组plan用来存储体积为j时候，能有几种装物品的方法，这个plan必须要根据价值是不是最大来判断是否更新。具体解释在代码里面。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.*;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Main</span> </span>&#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> mod = <span class="number">1000000007</span>;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">solve</span> <span class="params">(<span class="keyword">int</span>[] v,<span class="keyword">int</span>[] w,<span class="keyword">int</span> N,<span class="keyword">int</span> V)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[V + <span class="number">1</span>];</span><br><span class="line">        <span class="keyword">int</span>[] plan = <span class="keyword">new</span> <span class="keyword">int</span>[V + <span class="number">1</span>];<span class="comment">//体积为j时候，方案数是多少</span></span><br><span class="line">        plan[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">        <span class="comment">//需要把dp的初始状态变为-INF，表示体积恰好是j的时候，最大价值是多少</span></span><br><span class="line">        <span class="comment">//如果按照原来的算，j=10的时候，如果里面其实只装了6体积的物品，那么到底该用6体积的算还是用10算呢，</span></span><br><span class="line">        <span class="comment">//我又怎么知道，他只装了6体积呢</span></span><br><span class="line">        Arrays.fill(dp,<span class="number">1</span>,dp.length,-<span class="number">100000</span>);</span><br><span class="line">        </span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; N; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = V; j &gt;= v[i]; j--) &#123;</span><br><span class="line">                </span><br><span class="line">                    <span class="keyword">int</span> t = Math.max(dp[j], dp[j - v[i]] + w[i]);</span><br><span class="line">                    <span class="keyword">int</span> s = <span class="number">0</span>;</span><br><span class="line">                    <span class="keyword">if</span> (t == dp[j]) s += (plan[j] % mod);<span class="comment">//不放j，加上不放j的方案</span></span><br><span class="line">                    <span class="keyword">if</span> (t == (dp[j - v[i]] + w[i])) s += (plan[j - v[i]] % mod);<span class="comment">//加上放j的方案</span></span><br><span class="line">                    <span class="comment">//System.out.println(s);</span></span><br><span class="line">                    s %= mod;</span><br><span class="line">                    dp[j] = t;</span><br><span class="line">                    plan[j] = s;</span><br><span class="line">                </span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//show(dp);</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//show(plan);</span></span><br><span class="line">        <span class="keyword">int</span> maxw = <span class="number">0</span>;</span><br><span class="line">        <span class="comment">//因为不一定会用满，所以需要遍历</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; dp.length; i ++) &#123;</span><br><span class="line">            <span class="comment">//找到最大的价值</span></span><br><span class="line">            maxw = Math.max(dp[i],maxw);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//根据最大价值找到方案数</span></span><br><span class="line">        <span class="keyword">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; dp.length; i ++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (dp[i] == maxw) &#123;</span><br><span class="line">                ans += (plan[i] % mod); </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">show</span><span class="params">(<span class="keyword">int</span>[] arr)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//for (int i = 0; i &lt; arr.length; i++) &#123;</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt;arr.length; j++) &#123;</span><br><span class="line">                System.out.print(arr[j]+<span class="string">" "</span>);</span><br><span class="line">            &#125;</span><br><span class="line">            System.out.println();</span><br><span class="line">        <span class="comment">//&#125;</span></span><br><span class="line">        System.out.println(<span class="string">"*"</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span> <span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        Scanner sc=<span class="keyword">new</span> Scanner (System.in);</span><br><span class="line">        <span class="keyword">int</span> N,V;</span><br><span class="line">        <span class="comment">//while (sc.hasNext) &#123;</span></span><br><span class="line">            N = sc.nextInt();</span><br><span class="line">            V = sc.nextInt();</span><br><span class="line">            <span class="keyword">int</span>[] v = <span class="keyword">new</span> <span class="keyword">int</span>[N];<span class="comment">//体积</span></span><br><span class="line">            <span class="keyword">int</span>[] w = <span class="keyword">new</span> <span class="keyword">int</span>[N];<span class="comment">//价值</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; N; i++) &#123;</span><br><span class="line">                v[i] = sc.nextInt();</span><br><span class="line">                w[i] = sc.nextInt();</span><br><span class="line">            &#125;</span><br><span class="line">            System.out.println(solve(v,w,N,V));</span><br><span class="line">       <span class="comment">// &#125;</span></span><br><span class="line">    &#125;   </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h1 id="2-求背包的具体方案"><a href="#2-求背包的具体方案" class="headerlink" title="2.求背包的具体方案"></a>2.求背包的具体方案</h1><p>有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。</p>
<p>第 i 件物品的体积是 vi，价值是 wi。</p>
<p>求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。</p>
<p>输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。</p>
<p>输入格式<br>第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。</p>
<p>接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。</p>
<p>输出格式<br>输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。</p>
<p>物品编号范围是 1…N。</p>
<p>数据范围<br>0&lt;N,V≤1000<br>0&lt;vi,wi≤1000</p>
<hr>
<p><a href="https://www.acwing.com/problem/content/12/" target="_blank" rel="noopener">来源acwing</a><br>这次要选字典序小的，同时价值也得大。对于原来的方案，从最后一行遍历输出的话肯定是序号最大的，所以需要在一开始就要改变方法。采用贪心的策略，能选小的必须选小的。<br>转自dd大牛背包九讲：</p>
<blockquote>
<p>一般而言，求一个字典序最小的最优方案，只需要在转移时注意策略。首先，子问题的定义要略改一些。我们注意到，如果存在一个选了物品1的最优方案，那么答案一定包含物品1，原问题转化为一个背包容量为v-c[1]，物品为2..N的子问题。反之，如果答案不包含物品1，则转化成背包容量仍为V，物品为2..N的子问题。不管答案怎样，子问题的物品都是以i..N而非前所述的1..i的形式来定义的，所以状态的定义和转移方程都需要改一下。但也许更简易的方法是先把物品逆序排列一下，以下按物品已被逆序排列来叙述。</p>
</blockquote>
<blockquote>
<p>在这种情况下，可以按照前面经典的状态转移方程来求值，只是输出方案的时候要注意：从N到1输入时，如果f[i][v]==f[i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同时成立，应该按照后者（即选择了物品i）来输出方案。</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">solve</span> <span class="params">(<span class="keyword">int</span>[] v,<span class="keyword">int</span>[] w,<span class="keyword">int</span> N,<span class="keyword">int</span> V)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span>[][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[N + <span class="number">2</span>][V + <span class="number">1</span>];<span class="comment">//n+2是因为i+1会越界</span></span><br><span class="line">        </span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = N; i &gt;= <span class="number">1</span>; i--) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt;= V; j++) &#123;</span><br><span class="line">                    dp[i][j] = dp[i + <span class="number">1</span>][j];</span><br><span class="line">                    <span class="keyword">if</span> (j &gt;= v[i])</span><br><span class="line">                    dp[i][j] = Math.max(dp[i + <span class="number">1</span>][j], dp[i + <span class="number">1</span>][j - v[i]] + w[i]);</span><br><span class="line">                    </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">int</span> volume = V;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= N; i ++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (volume &gt;= v[i]) &#123;</span><br><span class="line">                <span class="keyword">if</span> (dp[i][volume] == dp[i + <span class="number">1</span>][volume - v[i]] + w[i]) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (i != N) &#123;</span><br><span class="line">                        System.out.print(i + <span class="string">" "</span>);</span><br><span class="line">                    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                        System.out.print(i);</span><br><span class="line">                    &#125;</span><br><span class="line">                    volume -= v[i];</span><br><span class="line"></span><br><span class="line">                &#125;</span><br><span class="line">            &#125;    </span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<p>   <strong>背包问题完</strong></p>

            <!--[if lt IE 9]><script>document.createElement('audio');</script><![endif]-->
            <audio id="audio" loop="1" preload="auto" controls="controls" data-autoplay="false">
                <source type="audio/mpeg" src="">
            </audio>
            
                <ul id="audio-list" style="display:none">
                    
                        
                            <li title='0' data-url='http://link.hhtjim.com/163/5146554.mp3'></li>
                        
                    
                        
                            <li title='1' data-url='http://link.hhtjim.com/qq/001faIUs4M2zna.mp3'></li>
                        
                    
                </ul>
            
        </div>
        
    <div id='gitalk-container' class="comment link"
        data-ae='false'
        data-ci='c82ee42088349c609c4d'
        data-cs='541eefaa06715f3b1bcd6bf41cb69a4053d18348'
        data-r='PPeony.github.io'
        data-o='PPeony'
        data-a='PPeony'
        data-d='false'
    >查看评论</div>


    </div>
    
</div>


    </div>
</div>
</body>

<script src="//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js"></script>


<script src="//lib.baomitu.com/jquery/1.8.3/jquery.min.js"></script>
<script src="/js/plugin.js"></script>
<script src="/js/diaspora.js"></script>


<link rel="stylesheet" href="/photoswipe/photoswipe.css">
<link rel="stylesheet" href="/photoswipe/default-skin/default-skin.css">


<script src="/photoswipe/photoswipe.min.js"></script>
<script src="/photoswipe/photoswipe-ui-default.min.js"></script>


<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">
    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>
    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">
        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>
        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">
            <div class="pswp__top-bar">
                <!--  Controls are self-explanatory. Order can be changed. -->
                <div class="pswp__counter"></div>
                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
                <button class="pswp__button pswp__button--share" title="Share"></button>
                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                      <div class="pswp__preloader__cut">
                        <div class="pswp__preloader__donut"></div>
                      </div>
                    </div>
                </div>
            </div>
            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div> 
            </div>
            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>
            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>
            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>
        </div>
    </div>
</div>




</html>
